package com.hanxiaozhang.sort;

import com.hanxiaozhang.util.AlgorithmUtil;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈快速排序相关问题〉
 *
 * @author hanxinghua
 * @create 2021/9/12
 * @since 1.0.0
 */
public class FastTopic {

    public static void main(String[] args) {
        int[] array1 = {2, 4, 6, 8, 11, 4, 2, 5, 7, 9};
        partition_1(array1, 8);
        System.out.println(Arrays.toString(array1));

        int[] array2 = {2, 4, 6, 8, 11, 4, 2, 5, 7, 9};
        partition_2(array2, 0, 9);
        System.out.println(Arrays.toString(array2));

    }


    /**
     * Partition问题：
     * 给定一个数组array，和一个整数target。请把小于等于target的数放在数组的左边，
     * 大于target的数放在数组的右边。
     * 要求额外空间复杂度O(1)，时间复杂度O(N)
     *
     * 我自己写方法，思路不对，容易写死了
     *
     * @param array
     * @param target
     */
    public static void partition_1(int[] array, int target) {
        int length = array.length;
        int index = 0;
        for (int i = 0; i < length; i++) {
            if (array[i] < target) {
                if (i != index) {
                    AlgorithmUtil.swap_2(array, index, i);
                }
                index++;
            }
        }
    }


    /**
     * Partition问题：
     * 右边界的数作为目标数
     *
     * @param array
     * @param L     左边界
     * @param R     右边界
     * @return
     */
    public static int partition_2(int[] array, int L, int R) {
        // 左大于右 返回 -1
        if (L > R) {
            return -1;
        }
        // 左等于右 返回 左
        if (L == R) {
            return L;
        }
        // 已经小于等于的位置
        int lessEqual = L - 1;
        // 需要比较的位置
        int index = L;
        // 循环
        while (index < R) {
            // 比较的位置小于目标值时，交换
            if (array[index] <= array[R]) {
                // i. ++lessEqual
                // ii.交换
                AlgorithmUtil.swap_1(array, index, ++lessEqual);
            }
            // 去下一个位置比较
            index++;
        }
        // 目标值R与++lessEqual位置交换，保证小于R的在左边，大于R的在右边
        AlgorithmUtil.swap_1(array, ++lessEqual, R);
        return lessEqual;
    }


    /**
     * 荷兰国旗问题
     * 给定一个数组array，和一个整数target。请把小于target的数放在数组的左边，
     * 等于target的数放在中间，大于target的数放在数组的右边。
     * 要求额外空间复杂度O(1)，时间复杂度O(N)
     *
     * @param array
     * @param L
     * @param R
     */
    public static int[] hollandFlag(int[] array, int L, int R) {
        if (L > R) {
            return new int[]{-1, -1};
        }
        if (L == R) {
            return new int[]{L, R};
        }
        // 小于区域的右边界
        int less = L - 1;
        // 大于区域的左边界
        int more = R;
        // 需要比较的位置
        int index = L;
        // 循环  R位置元素，为目标元素
        while (index < more) {
            // 需要比较的位置元素值 等于 R位置元素值时，需要比较的位置后移一位
            if (array[index] == array[R]) {
                index++;

                // 需要比较的位置元素值 小于 R元素值时
            } else if (array[index] < array[R]) {
                // i. 小于区域的右边界后移一位
                // ii. 交换
                // iii. 需要比较的位置后移一位
                AlgorithmUtil.swap_1(array, index, ++less);
                index++;
                // 需要比较的位置元素值 大于 R元素值时
            } else {
                // i. 大于区域的左边界前移一位
                // ii. 交换
                AlgorithmUtil.swap_1(array, index, --more);
            }
        }
        // 目标元素R 与 more交换
        AlgorithmUtil.swap_1(array, more, R);
        // 返回
        return new int[]{less + 1, more};
    }


}
